package algo.combinatorics
/*
 Problem Statement

Gandalf is travelling from Rohan to Rivendell to meet Frodo but there is no direct route from Rohan (T1) to Rivendell (Tn).

But there are towns T2,T3,T4...Tn-1 such that there are N1 routes from Town T1 to T2, and in general, Ni routes from Ti to Ti+1 for i=1 to n-1 and 0 routes for any other Ti to Tj for j ≠ i+1

Find the total number of routes Gandalf can take to reach Rivendell from Rohan.

Note 
Gandalf has to pass all the towns Ti for i=1 to n-1 in numerical order to reach Tn. 
For each Ti , Ti+1 there are only Ni distinct routes Gandalf can take.

Input Format 
The first line contains an integer T, T test-cases follow. 
Each test-case has 2 lines. The first line contains an integer N (the number of towns). 
The second line contains N - 1 space separated integers where the ith integer denotes the number of routes, Ni, from the town Ti to Ti+1

Output Format 
Total number of routes from T1 to Tn modulo 1234567 
http://en.wikipedia.org/wiki/Modular_arithmetic

Constraints 
1 <= T<=1000
2< N <=100
1 <= Ni <=1000
 */
import scala.collection.mutable.ListBuffer

object Solution {
  
  val routesList = ListBuffer[String]()
  
  def main(args: Array[String]) {
    val testCount = readLine
    for (i <- 0 until testCount.toInt) {
      val numTowns = readLine
      val numRoutesStr = readLine
      routesList += numRoutesStr
    }
    
    routesList.foreach({ route =>
      val numRoutes = route.split(" ").map(_.toInt)
      var res = BigInt(1)
      for (i <- 0 until numRoutes.length) {
        res = res * numRoutes(i)
      }
      println(res % 1234567)
    })

  }

}